class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        diagram = [0] * (len(height)-1)
        maxIndexFromLeft = 0
        maxIndexFromRight = 0
        maxHeight = 0

        for i in range(len(height)):
            if height[i] > maxHeight:
                maxHeight = height[i]
                maxIndexFromLeft = i
        for i in range(len(height)-1, -1, -1):
            if height[i] == maxHeight:
                maxIndexFromRight = i
                break
        
        maxFromLeft = 0
        for i in range(0, maxIndexFromLeft):
            maxFromLeft = max(maxFromLeft, height[i])
            diagram[i] = maxFromLeft
        maxFromRight = 0
        for i in range(len(height)-1, maxIndexFromRight, -1):
            maxFromRight = max(maxFromRight, height[i])
            diagram[i-1] = maxFromRight
        for i in range(maxIndexFromLeft, maxIndexFromRight):
            diagram[i] = maxHeight
        
        begin = 0 #begin of max diagram from left
        end = 0 # begin of max diagram from right
        maxDiagram = 0
        for dia in diagram:
            maxDiagram = max(maxDiagram, dia)
        for i, dia in enumerate(diagram):
            if dia == maxDiagram:
                begin = i
                break
        for i in range(len(diagram)-1, -1, -1):
            if diagram[i] == maxDiagram:
                end = i
                break

        curHeight = min(diagram[begin], diagram[end])
        maxSize = curHeight * (end-begin+1)
        while begin != 0 and end != len(diagram)-1:
            if diagram[begin-1] > diagram[end+1]:
                begin = begin-1
            else:
                end = end+1
            curHeight = min(diagram[begin], diagram[end])
            size = curHeight * (end-begin+1)
            maxSize = max(maxSize, size)
        
        if begin == 0:
            while end != len(diagram)-1:
                end = end + 1
                curHeight = min(diagram[begin], diagram[end])
                size = curHeight * (end-begin+1)
                maxSize = max(maxSize, size)
        if end == len(diagram)-1:
            while begin != 0:
                begin = begin - 1
                curHeight = min(diagram[begin], diagram[end])
                size = curHeight * (end-begin+1)
                maxSize = max(maxSize, size)
        
        return maxSize
s = Solution()
what = [1,2,4,3]
print(s.maxArea(what))